﻿#include <stdio.h>
#include <stdlib.h>

typedef int E;
typedef struct MinHeap {
    E *arr;
    int size;
    int capacity;
} *Heap;

_Bool initHeap(Heap heap) {
    heap->size = 0;
    heap->capacity = 11;
    heap->arr = malloc(sizeof(E) * heap->capacity);
    return heap->arr != NULL;
}

_Bool insert(Heap heap, E element) {
    if (heap->size == heap->capacity) return 0;
    int index = ++heap->size;
    while (index > 1 && element < heap->arr[index / 2]) {
        heap->arr[index] = heap->arr[index / 2];
        index /= 2;
    }
    heap->arr[index] = element;
    return 1;
}

E delete(Heap heap) {
    E max = heap->arr[1], e = heap->arr[heap->size--];
    int index = 1;
    while (index * 2 <= heap->size) {
        int child = index * 2;
        if (child < heap->size && heap->arr[child] > heap->arr[child + 1])
            child += 1;
        if (e <= heap->arr[child]) break;
        else heap->arr[index] = heap->arr[child];
        index = child;
    }
    heap->arr[index] = e;
    return max;
}

int main() {
    int arr[] = {3, 5, 7, 2, 9, 0, 6, 1, 8, 4};
    struct MinHeap heap;    //先创建堆
    initHeap(&heap);
    for (int i = 0; i < 10; ++i)
        insert(&heap, arr[i]);   //直接把乱序的数组元素挨个插入
    for (int i = 0; i < 10; ++i)
        arr[i] = delete(&heap);    //然后再一个一个拿出来，就是按顺序的了

    for (int i = 0; i < 10; ++i)
        printf("%d ", arr[i]);
    return 0;
}
